class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


import functools


class Solution(object):
    def minCameraCover(self, root):
        @functools.cache
        def dfs1(node):
            if not node:
                return 0
            ans1 = min(dfs1(node.left), dfs2(node.left))
            ans2 = min(dfs1(node.right), dfs2(node.right))
            return 1 + ans1 + ans2
        @functools.cache
        def dfs2(node):
            if not node:
                return 0
            ans1 = min(dfs1(node.left), dfs3(node.left))
            ans2 = min(dfs1(node.right), dfs3(node.right))
            return ans1 + ans2
        @functools.cache
        def dfs3(node):
            if not node:
                return 0
            if node.left:
                if node.right:
                    ans1 = dfs1(node.left) + dfs3(node.right)
                    ans2 = dfs1(node.left) + dfs1(node.right)
                    ans3 = dfs3(node.left) + dfs1(node.right)
                    return min(ans1, ans2, ans3)
                else:
                    return dfs1(node.left)
            else:
                if node.right:
                    return dfs1(node.right)
                else:
                    return float('inf')

        return min(dfs1(root), dfs3(root))
